//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 子数组 是数组中的一个连续部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：nums = [5,4,-1,7,8]
//输出：23
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// -10⁴ <= nums[i] <= 10⁴ 
// 
//
// 
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。 
//
// Related Topics 数组 分治 动态规划 👍 6680 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-06-05 14:20:49
 * @description 53.最大子数组和
 */
public class MaximumSubarray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MaximumSubarray fun=new MaximumSubarray();
	 	 Solution solution = fun.new Solution();
		  int [] ar= new int[]{1};
		 System.out.println(solution.maxSubArray2(ar));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
 class Solution {
	/*暴力*/
	public int maxSubArray1(int[] nums) {
		int res=-10000,t=0;
		for (int i = 0; i < nums.length ;i++) {
			t=0;
			for (int j = i; j<nums.length ; j++) {
				t+=nums[j];
				res=Math.max(res,t);
			}
		}
		return  res;
	}
	/*动态规划 时间On  空间On*/
	public int maxSubArray2(int[] nums) {
		int res=nums[0];
		int len = nums.length;
		int []dp=new int[len];
		dp[0]=nums[0];
		for (int i = 1; i < nums.length ;i++) {
			dp[i] =Math.max(dp[i-1]+nums[i],nums[i]);
			res=Math.max(res,dp[i]);
		}
		return  res;
	}
	/*
	* 动态规划 空间O1
	* */
	public int maxSubArray3(int[] nums) {
		int res=nums[0];
		int p=0;
		for (int i = 1; i < nums.length ;i++) {
			p =Math.max(p+nums[i],nums[i]);
			res=Math.max(res,p);
		}
		return  res;
	}
	/*贪心时间On  空间O1*/
	public int maxSubArray4(int[] nums) {
		int res = -10000,sum=0;
		int len = nums.length;
		for (int i = 0; i < len ; i++) {
			sum+=nums[i];
			//如果全是负数，保存的会是最大的负数也不影响结果
			res=Math.max(res,sum);
			//当和为0时，从小开始计算
			if(sum<0) sum=0;
		}
		return res;
	}
	/*分治法 时间Onlogn  空间Ologn
	 * 取中间，要么在左边，要么在右边，要么跨两把*/
	public int maxSubArray5(int[] nums) {
		int res = -10000,sum=0;
		int len = nums.length;
		if (len==0) return 0;
		return maxSubSum(nums,0,len-1);
	}
	private int maxCross(int[] nums,int l,int mid,int r){
		int sum=0;
		int lSum=-10000;
		int rSum=-10000;
		//计算以mid结尾左边最大子数组和
		for (int i = mid; i >=l  ; i--) {
			sum+=nums[i];
			if(sum>lSum){
				lSum=sum;
			}
		}
		sum=0;
		//计算右边
		for (int i = mid+1; i < r; i++) {
			sum+=nums[i];
			if(sum>rSum){
				rSum=sum;
			}
		}
		return  lSum+rSum;
	}
	//单侧
	private int maxSubSum(int[] nums,int l,int r){
		if(l==r){
			return  nums[l];
		}
		int mid=l+(r-l)/2;
		return Math.max(Math.max(maxSubSum(nums,l,mid),maxSubSum(nums,mid+1,r)) ,maxCross(nums,l,mid,r));
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
